Алгоритмы планирования¶

Планировщик — это часть ядра, которая решает какой запущенный процесс будет выполняться процессором следующим. Каждому процессу назначается алгоритм планирования и статический приоритет планирования, sched_priority; эти параметры изменяются вызовом sched_setscheduler(). Планировщик принимает решение на основе данных об алгоритме планирования и статическом приоритете всех процессов системы.

Для процессов, которые планируются одним из обычных алгоритмом планирования (SCHED_OTHER, SCHED_IDLE, SCHED_BATCH), значение sched_priority при принятии решения не используется (должен быть указан 0).

Для процессов, которые планируются одним из алгоритмов реального времени (SCHED_FIFO, SCHED_RR), значение приоритета sched_priority лежит в диапазоне от 1 (низкий) до 99 (высокий). Как и числовые значения, процессы реального времени всегда имеют более высокий приоритет чем обычные процессы. Но заметим: согласно POSIX.1-2001 от реализации для алгоритмов реального времени требуется поддержка минимум 32 различных уровней приоритета, и в некоторых системах обеспечивается только этот минимум. В переносимых программах нужно использовать вызовы sched_get_priority_min(2) и sched_get_priority_max(2) для для определения диапазона приоритетов, поддерживаемых определённым алгоритмом.

По существу, планировщик хранит в памяти списки всех работающих процессов для каждого возможного значения sched_priority. Чтобы определить какой процесс выполнять следующим, планировщик ищет непустой список с самым высоким статическим приоритетом и выбирает процесс из начала списка.

Алгоритм планирования определяет, в какое место списка будет добавлен процесс с тем же статическим приоритетом и как он будет перемещаться внутри этого списка.

Всё планирование основано на вытеснении: если процесс с высшим статическим приоритетом готов к выполнению, текущий выполняющийся процесс будет вытеснен и возвращён в список ожидания согласно своему уровню статического приоритета. Алгоритм выполнения только определяет порядок внутри списка готовых к выполнению процессов с одинаковым статическим приоритетом.

SCHED_FIFO: планировщик «первым вошёл — первым выше뻶

Алгоритм SCHED_FIFO можно использовать только со значениями статического приоритета большими нуля. Это означает, что если процесс с SCHED_FIFO готов к работе, то он сразу запустится, а все обычные процессы с SCHED_OTHER, SCHED_BATCH или SCHED_IDLE будут приостановлены. SCHED_FIFO — это простой алгоритм планирования без квантования времени. Процессы, работающие согласно алгоритму SCHED_FIFO, подчиняются следующим правилам:

• Процесс с алгоритмом SCHED_FIFO, приостановленный другим процессом с большим приоритетом, останется в начале списка процессов с равным приоритетом, и его исполнение будет продолжено сразу после того, как закончатся процессы с большими приоритетами.
• Когда процесс с алгоритмом SCHED_FIFO готов к работе, он помещается в конец списка процессов с тем же приоритетом.
• Вызов sched_setscheduler() или sched_setparam(2), поместит процесс с номером pid и алгоритмом SCHED_FIFO (или SCHED_RR) в начало списка процессов, если он запускаем. Как следствие, он может вытеснить выполняющийся в данный момент процесс, если он имеет такой же приоритет. (В POSIX 1003.1 указано, что процесс должен перейти в конец списка).
• Процесс, вызывающий sched_yield(2), будет помещён в конец списка.

Других событий для перемещения процесса с алгоритмом SCHED_FIFO в списке ожидания запускаемых процессов с одинаковым статическим приоритетом не существует.

Процесс с алгоритмом SCHED_FIFO выполняется до тех пор, пока не будет заблокирован запросом ввода/вывода, вытеснен процессом с большим приоритетом или пока не вызовет sched_yield(2).

SCHED_RR: планирование выполнения по циклу¶

SCHED_RR — это просто улучшение SCHED_FIFO. Всё, относящееся к SCHED_FIFO, справедливо и для SCHED_RR за исключением того, что каждому процессу разрешено работать непрерывно не дольше максимального кванта времени. Если процесс с алгоритмом SCHED_RR работал столько же или дольше, чем квант, то он помещается в конец списка с тем же приоритетом. Процесс с алгоритмом SCHED_RR, вытесненный процессом с большим приоритетом, возобновляя работу, использует остаток своего кванта из старого цикла. Длину этого кванта можно узнать, вызвав sched_rr_get_interval(2).

SCHED_OTHER: планирование с разделение времени (по умолчанию в Linux)¶

SCHED_OTHER можно использовать только с статическим приоритетом равным нулю. SCHED_OTHER — это стандартный планировщик Linux с разделением времени, предназначенный для всех процессов, не требующих специальных механизмов реального времени. Для выполнения выбирается процесс из списка со статическим приоритетом 0 на основе динамического приоритета, существующего только внутри этого списка. Динамический приоритет основан на значении nice (установленном при помощи nice(2) или setpriority(2)) и увеличивается с каждым квантом времени, при котором процесс был готов к работе, но ему было отказано в этом планировщиком. Таким образом время равномерно распределяется между всеми процессами с алгоритмом SCHED_OTHER.

SCHED_BATCH: планирование для пакетных процессов¶

(начиная с Linux 2.6.16) SCHED_BATCH можно использовать только с статическим приоритетом равным нулю. Этот алгоритм похож на SCHED_OTHER в том, что он планирует выполнение процесса на основе его динамического приоритета (на основе значения nice). Различие в том, что в этом алгоритме планировщик всегда предполагает, что процесс в основном использует ЦП. Следовательно, планировщик немного понизит вероятность его следующего пробуждения для того, чтобы этот процесс уступал другим при планировании.

Этот алгоритм полезен при нагрузках неинтерактивными задачами, но когда нежелательно понижать их значение nice и для задач, которым требуется предсказуемый алгоритм планирования без интерактивности, который приводит к дополнительным вытеснениям (между задачами нагрузки).

SCHED_IDLE: планирование заданий с очень низким приоритетом¶

(начиная с Linux 2.6.23) SCHED_IDLE можно использовать только с статическим приоритетом равным нулю; значение nice не учитывает в этом алгоритме.

Данный алгоритм предназначен для выполнения заданий с чрезвычайно низким приоритетом (даже ниже чем значение nice +19 в алгоритме SCHED_OTHER или SCHED_BATCH).

Сброс алгоритма планирования у дочерних процессов¶

Начиная с Linux 2.6.32, при вызове sched_setscheduler() к policy может быть добавлен флаг SCHED_RESET_ON_FORK (с помощью OR). В результате потомки, созданные с помощью fork(2), не будут наследовать привилегированные алгоритмы планирования. Эта возможность предназначена для приложений, проигрывающих медиа-файлы, и может использоваться для обхождения ограничения ресурса RLIMIT_RTTIME (см. getrlimit(2)), посредством создания нескольких дочерних процессов.

Точнее говоря, если указан флаг SCHED_RESET_ON_FORK, то к новым потомкам применяются следующие правила:

• Если вызывающий процесс имеет алгоритм планирования SCHED_FIFO или SCHED_RR, то у потомков алгоритм сбрасывается в SCHED_OTHER.
• Если у вызывающего процесса значение nice отрицательно, то у потомков значение nice сбрасывается в ноль.

После установки флага SCHED_RESET_ON_FORK его можно сбросить только, если процесс имеет мандат CAP_SYS_NICE. Этот флаг выключается у потомков, созданных через fork(2).

Флаг SCHED_RESET_ON_FORK видим в значении алгоритма, которое возвращается sched_getscheduler().

Привилегии и ограничения по ресурсам¶

В ядрах Linux до версии 2.6.12, только привилегированные процессы (CAP_SYS_NICE) могли устанавливать ненулевое значение статического приоритета (т.е. алгоритм планирования реального времени). Непривилегированные процессы могли только установить алгоритм SCHED_OTHER, и это могло быть сделано только если эффективный пользовательский идентификатор вызывающего sched_setscheduler() совпадал с реальным или эффективным пользовательским идентификатором задаваемого процесса (т.е., процесса, указываемого в pid).

Начиная с Linux 2.6.12, ограничитель ресурса RLIMIT_RTPRIO определяет максимум статического приоритета непривилегированного процесса для алгоритмов SCHED_RR и SCHED_FIFO. Правила для изменения алгоритма планирования и приоритета:

• Если непривилегированный процесс имеет ненулевое значение мягкого ограничения RLIMIT_RTPRIO, то он может изменять свой алгоритм планирования и приоритет, но при этом значение приоритета не может быть больше чем максимальное значение его текущего приоритета и его мягкого ограничения RLIMIT_RTPRIO.
• Если мягкое ограничение RLIMIT_RTPRIO равно 0, то разрешается только снижать приоритет или переключиться на алгоритм выполнения не реального времени.
• Согласно тем же самым правилам другой непривилегированный процесс может также сделать эти изменения, пока эффективный идентификатор пользователя процесса, производящего изменение, совпадает с реальным или эффективным идентификатором пользователя изменяемого процесса.
• Для SCHED_IDLE применяются специальные правила. В ядрах Linux до версии 2.6.39, сменить политику работы непривилегированного процесса нельзя, независимо от значения его ограничителя ресурсов RLIMIT_RTPRIO. В ядрах Linux начиная с версии 2.6.39, непривилегированный процесс может переключиться на политику SCHED_BATCH или SCHED_NORMAL, если его значение уступчивости находится в диапазоне, разрешённом ему ограничителем ресурсов RLIMIT_NICE (смотрите getrlimit(2)).

Для привилегированных (CAP_SYS_NICE) процессов ограничение RLIMIT_RTPRIO игнорируется; как в старых ядрах, они могут произвольно менять алгоритм планирования и приоритет. Подробней смотрите в getrlimit(2) про RLIMIT_RTPRIO.

Время ответа¶

Блокированный процесс с высоким приоритетом, ожидающий ввода/вывода, освобождает достаточно много процессорного времени до того, как снова начнёт работать. Авторы драйверов устройств могут более эффективно использовать это время, если воспользуются «медленным» обработчиком прерываний.

Разное¶

Дочерние процессы наследуют алгоритм планирования и его параметры после fork(2). Алгоритм планирования и параметры сохраняются при вызове execve(2).

Обычно, процессам реального времени необходимо блокировать память для того, чтобы избежать задержек при страничном обмене. Это можно сделать при помощи вызова mlock(2) или mlockall(2).

Так как неблокирующий бесконечный цикл в процессе, работающем по алгоритму SCHED_FIFO или SCHED_RR, может навсегда заблокировать все процессы с меньшим приоритетом, разработчик таких программ должен всегда оставлять на одном из терминалов консоли оболочку, имеющую больший статический приоритет, чем приоритет тестируемой программы. Это позволит прекратить работу отлаживаемого приложения реального времени, которое работает не так, как ожидается. Также смотрите описание ресурса RLIMIT_RTTIME в getrlimit(2).

В системах POSIX, в которых доступны sched_setscheduler() и sched_getscheduler(), в <unistd.h> определён макрос _POSIX_PRIORITY_SCHEDULING.

Возможности выполнения в реальном времени из оригинальной версии Linux¶

Начиная с версии 2.6.18 Linux постепенно обрастает возможностями выполнения в реальном времени, большая часть которых взята из ранних заплаток realtime-preempt, разработанных Ingo Molnar, Thomas Gleixner, Steven Rostedt и другими. Пока заплатки полностью не вошли в оригинальное ядро (ожидается к версии 2.6.30), они должны быть установлены отдельно. Файлы заплаток называются

patch-версия_ядра-rtверсия_заплатки

и могут быть скачаны с http://www.kernel.org/pub/linux/kernel/projects/rt/.

Без заплаток и до их полного включения в оригинальное ядро, через параметры ядра предлагается только три класса вытеснения: CONFIG_PREEMPT_NONE, CONFIG_PREEMPT_VOLUNTARY и CONFIG_PREEMPT_DESKTOP, которые, соответственно, не сокращают, частично сокращают и значительно сокращают задержку планирования при наихудшем случае.

С заплатками и после их полного включения в оригинальное ядро, в параметрах ядра появится новый пункт CONFIG_PREEMPT_RT. Если он будет выбран, то Linux преобразуется в обычную операционную систему реального времени. Алгоритмы планирования FIFO и RR, которые можно выбрать с помощью sched_setscheduler(), используются для выполнения процесса с настоящим приоритетом реального времени и минимальной задержкой планирования в наихудшем случае.